package 中等;

public class 从前序与中序遍历序列构造二叉树 {

    public static void main(String[] args) {
        int[] preorder = {9,3,15,20,7};
        int[] inorder = {9,15,7,20,3};
        System.out.println(buildTree1(preorder,inorder ));



    }

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder,0 ,preorder.length-1
                    ,inorder ,0  ,inorder.length-1 );
    }

    public static TreeNode build(int[] preorder ,int pStart,int pEnd
                                ,int[] inorder  ,int iStart,int iEnd) {
        if (pStart > pEnd || iStart > iEnd){
            return null;
        }
        int rootVal = preorder[pStart];
        TreeNode root = new TreeNode(rootVal);
        int iIndex = iStart;
        while (inorder[iIndex] != rootVal){
            iIndex++;
        }
        int leftNum = iIndex - iStart;
        int pIndex = leftNum + pStart;
        root.left = build(preorder,pStart+1 ,pIndex
                         ,inorder ,iStart ,iIndex-1 );
        root.right = build(preorder,pIndex+1 ,pEnd
                          ,inorder ,iIndex+1 ,iEnd );

        return root;
    }
    //106. 从中序与后序遍历序列构造二叉树
    public static TreeNode buildTree1(int[] inorder, int[] postorder) {
        return build1(inorder,0 ,inorder.length-1
                ,postorder ,0  ,postorder.length-1 );
    }

    public static TreeNode build1(int[] inorder ,int iStart,int iEnd
            ,int[] postorder  ,int pStart,int pEnd) {
        if (pStart > pEnd || iStart > iEnd){
            return null;
        }
        int rootVal = postorder[pEnd];
        TreeNode root = new TreeNode(rootVal);
        int iIndex = iStart;
        while (inorder[iIndex] != rootVal){
            iIndex++;
        }
        int leftNum = iIndex - iStart;
        int pIndex = pStart + leftNum;
        root.left = build(inorder,iStart ,iIndex-1
                ,postorder ,pStart ,pIndex-1);
        root.right = build(inorder,iIndex+1 ,iEnd
                ,postorder ,pIndex ,pEnd-1 );

        return root;
    }
}
